package longestPalindrome5;

public class LongestPalindrome {

    public String longestPalindrome(String s) {
        //初始化第一个字符默认为最长
        String  maxStr =s.substring(0,1);
        int len = s.length();
        //dp[i][j] 表示 区间范围 [i,j]（左闭右闭）的字串是否是回文串，如果是，则 dp[i][j] 为 true；反之，为 false
        boolean[][] dp = new boolean[len][len];
        //找子串，右边界右移动
        for(int right = 1;right < len; right++){
            //左边从0开始寻找到右边界为止的所有子串，如果连个边界位置字符相同则有可能是回文串，需要判断里面的left+1与right-1是否是相同字符
            for(int left=0;left < right;left++){
                if(s.charAt(left) != s.charAt(right)){
                    //说明不是回文子串
                    dp[left][right] = false;
                    continue;
                }
                if(left+1>=right-1){//左侧边界与右侧重合
                    dp[left][right] = true;
                }else{
                    //左右字符相等，那么我们判断中间的就是left+1与right-1是不是相等
                    dp[left][right] = dp[left+1][right-1];
                }
                //如果都相等也就是dp[left+1][right-1]为true则right-left+1这个位置就是最长的回文字符所在位置
                if(dp[left][right] && right-left+1 > maxStr.length()){
                    maxStr = s.substring(left,right+1);
                }
            }
        }
        return maxStr;
    }


    public static void main(String[] args) {
        LongestPalindrome longestPalindrome = new LongestPalindrome();
        System.out.println(longestPalindrome.longestPalindrome("bb"));

    }

}